package solution.math;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class NextLargerWithSameBits {

	/**
	 * check http://www.sureinterview.com/shwqst/40004
	 * 
	 * NOTE: overflow is not considered.
	 * 
	 * @param num
	 * @return the next larger number with same number of set bits
	 */
	int getNextLarger(int num) {
		if (num == 0 || num == -1)
			return num;

		// (1) add 1 to the last set bit
		int lastSetBit = num & ~(num - 1);
		int largerNum = num + lastSetBit;

		// (2) move the changed bits to the least significant bits. (right side)
		int fb = num ^ largerNum; // flipped bits
		int lastBits = fb / lastSetBit; // move flipped bits to the right and
										// discard two bits after moving.
		lastBits >>= 2;

		// (3) move bits to maintain the same number of set bits.
		largerNum |= lastBits;
		return largerNum;
	}

	String getSetBits(int num) {
		String prt = "";
		for (int i = 0; i < 32; i++) {
			if ((num & 1) == 1) {
				prt += i + " ";
			}
			num >>>= 1;
		}
		return prt;
	}

	@Test
	public void test() {
		int num = 0x7;

		// next larger
		for (int i = 0; i < 30; i++) {
			num = getNextLarger(num);
			System.out.println(Integer.toBinaryString(num) + " "
					+ getSetBits(num));
		}

		System.out.println("---");

		// next smaller
		num = 0x700;
		for (int i = 0; i < 30; i++) {
			num = ~getNextLarger(~num);
			System.out.println(Integer.toBinaryString(num) + " "
					+ getSetBits(num));
		}

	}

}
